Array.prototype.findSort = function (num1) {
  var hasSortArr = this
  var l = 0; var r = hasSortArr.length
  var lock = -1
  var dis = 0
  var dis1 = 0; var dis2 = 0
  if (hasSortArr.length > 0) {
    dis1 = num1 - hasSortArr[0]
    if (dis1 <= 0) {
      return [0, dis1]
    }
    dis2 = num1 - hasSortArr[r - 1]
    if (dis2 >= 0) {
      return [r - 1, dis2]
    }
    while (lock === -1) {
      var m = (l + r + 1) >> 1
      // 比较下坐标大小
      dis = num1 - hasSortArr[m]
      if (dis > 0) {
        if (m + 1 === r) {
          if (dis > -dis2) {
            lock = r
            dis = dis2
          } else {
            lock = m
          }
        } else {
          dis1 = dis
          l = m
        }
      } else if (dis < 0) {
        if (l + 1 === m) {
          if (-dis >= dis1) {
            lock = l
            dis = dis1
          } else {
            lock = m
          }
        } else {
          dis2 = dis
          r = m
        }
      } else {
        lock = m
      }
    }
    return [lock, dis]
  }
  return [lock, dis]
}
// 比较两字符的相等长度和大小
function compareLen (n1, n2, str1, str2) {
  // 求出相等部分
  var len = 0
  let dis = 0
  let lock = true
  while (dis === 0 && lock) {
    var c1 = str1.charCodeAt(n1 + len)
    var c2 = str2.charCodeAt(n2 + len)
    if (n1 + len < str1.length && n2 + len < str2.length) {
      if (c1 > c2) {
        dis = 1
      } else if (c1 < c2) {
        dis = -1
      } else if (c1 === c2) {
        len++
      }
    } else if (n1 + len >= str1.length && n2 + len >= str2.length) {
      lock = false
    } else if (n1 + len < str1.length) {
      dis = 1
    } else if (n2 + len < str2.length) {
      dis = -1
    }
  }
  return [len, dis]
}

// 查找字符在数组的最大相等长度和大小
function findLen (str, hasSortArr, callback) {
  var l = 0; var r = hasSortArr.length
  var lock = -1
  var len1 = 0; var len2 = 0
  var len = 0; var dis = 0

  if (hasSortArr.length > 0) {
    [len1, dis] = callback(str, hasSortArr[0])
    if (dis < 1) {
      return [0, len1, dis]
    }
    [len2, dis] = callback(str, hasSortArr[r - 1])
    if (dis > -1) {
      return [r - 1, len2, dis]
    }
    while (lock === -1) {
      var m = (l + r + 1) >> 1;
      // 比较下坐标大小
      [len, dis] = callback(str, hasSortArr[m])

      if (dis === 1) {
        if (m + 1 === r) {
          if (len < len2) {
            lock = r
            len = len2
            dis = -1
          } else {
            lock = m
          }
        } else {
          len1 = len
          l = m
        }
      } else if (dis === -1) {
        if (l + 1 === m) {
          if (len < len1) {
            lock = l
            len = len1
            dis = 1
          } else {
            lock = m
          }
        } else {
          len2 = len
          r = m
        }
      } else {
        lock = m
      }
    }
    return [lock, len, dis]
  }
  return [lock, 0, 1]
}

class SearchClass {
  constructor (data) {
    this.data = data

    var bitMap1 = []
    var bitMap2 = []
    data.forEach(function (str, j) {
      for (let i = 0; i < str.length; i++) {
        bitMap1.push(i)
        bitMap2.push(j)
      }
    })
    this.bitMap1 = bitMap1
    this.bitMap2 = bitMap2
    this.saArr = this.getSa()
  }

  getSa () {
    var data = this.data
    var bitMap1 = this.bitMap1
    var bitMap2 = this.bitMap2
    var sLen = bitMap1.length// 总共排名长度
    // 后缀数组
    var sa = []
    for (var i = 0; i < sLen; i++) {
      var [n, len, dis] = findLen(i, sa, function (n1, n2) {
        return compareLen(bitMap1[n1], bitMap1[n2], data[bitMap2[n1]], data[bitMap2[n2]])
      })
      if (dis === 1) {
        sa.splice(n + 1, 0, i)
      } else {
        sa.splice(n, 0, i)
      }
    }
    return sa
  }

  _getList (key) {
    const bitMap1 = this.bitMap1
    const bitMap2 = this.bitMap2
    const data = this.data
    const saArr = this.saArr

    const list = []
    let preArr
    for (let i = 0; i < key.length; i++) {
      var [n, len, dis] = findLen(i, saArr, function (n1, n2) {
        return compareLen(n1, bitMap1[n2], key, data[bitMap2[n2]])
      })
      if (len > 0) {
        if (preArr) {
          if (i + len > preArr[0] + preArr[1]) {
            preArr = [i, len, n]
            list.push(preArr)
          }
        } else {
          preArr = [i, len, n]
          list.push(preArr)
        }
      }
    }
    list.sort(function (p1, p2) {
      return p2[1] - p1[1]
    })
    return list
  }

  getList (key) {
    const bitMap1 = this.bitMap1
    const bitMap2 = this.bitMap2
    const data = this.data
    const saArr = this.saArr

    const list = this._getList(key)

    const rangeList = []
    const pageList = []
    list.forEach(function ([m, len, n]) {
      let n1 = n
      let direction = -1
      while (direction !== 0) {
        if (direction === -1 && n1 === -1) {
          direction = 1
          n1 = n + 1
        } else if (direction === 1 && n1 === saArr.length) {
          direction = 0
        } else {
          const index = bitMap2[saArr[n1]]
          if (pageList.indexOf(index) === -1) {

            let isHas = true
            const str = data[index]
            const mid = bitMap1[saArr[n1]]

            const leftMin = mid > m ? m : mid
            const rlen1 = str.length - mid-len
            const rlen2 = key.length - m-len

            const rightMin = rlen1 > rlen2 ? rlen2 : rlen1
            let sLen = 0
            for (let i = -leftMin; i < len + rightMin; i++) {
              if (str[mid + i] === key[m + i]) {
                sLen++
              } else if (i >= 0 && i < len) {
                isHas = false
                break
              }
            }

            if (isHas) {
              pageList.push(index)
              const mLen = leftMin + len + rightMin
              rangeList.push([index, sLen, mid - leftMin, mLen, m - leftMin])
              n1 = n1 + direction
            } else if (direction === -1) {
              direction = 1
              n1 = n + 1
            } else {
              direction = 0
            }
          } else {
            n1 = n1 + direction
          }
        }
      }
    })
    rangeList.sort(function (p1, p2) {
      if (p1[1] === p2[1]) {
        if (p1[3] === p2[3]) {
          if (p1[4] === p2[4]) {
            return p1[0] - p2[0]
          }
          return p1[4] - p2[4]
        }
        return p1[3] - p2[3]
      }
      return p2[1] - p1[1]
    })
    return rangeList;
  }
}
export default SearchClass

// const obj = new SearchClass(['123rrrr', '23', '2340', '2350'])
// const list = obj.getList('34002323403400232340')
// console.log(list)
